package leetcode.weekly.week329;

//Solution4Test
public class Solution4 {

	public int minCost(int[] nums, int k) {
		int len = nums.length;
		long[] dp = new long[len];
		dp[0] = k;
		for (int i = 1; i < len; i++) {
			long cur = Long.MAX_VALUE;
			int[] h = new int[len];
			int show1 = 0;
			for (int j = i; j >= 0; j--) {
				int num = nums[j];
				h[num]++;
				if (h[num] == 1) {
					show1++;
				} else if (h[num] == 2) {
					show1--;
				}
				long cost = i - j + 1 - show1 + k;
				if (j > 0) {
					cost += dp[j - 1];
				}
				cur = Math.min(cur, cost);
			}
			dp[i] = cur;
		}
		return (int) dp[len - 1];
	}
}
